package leetcode.动态规划.middle;

import java.util.Arrays;

/**
 * @author wangmaolin1
 * @date 2023/11/14 22:30
 */
public class _1143 {
    int[][]bk;
    public int longestCommonSubsequence(String text1, String text2) {
       bk=new int[text1.length()+1][text2.length()+1];
        for (int[] ints : bk) {
            Arrays.fill(ints,-1);
        }
        return  dp(text1,0,text2,0);
    }

    private int dp(String text1, int i, String text2, int j) {
        if (i>=text1.length() || j >=text2.length()){
            return 0;
        }
        if (bk[i][j]!=1){
            return bk[i][j];
        }
        if (text1.charAt(i)==text2.charAt(j)){
            bk[i][j] =  1+dp(text1,i+1,text2,j+1);
        }else {
            bk[i][j] = Math.max(dp(text1,i+1,text2,j),Math.max(dp(text1,i,text2,j+1),dp(text1,i+1,text2,j+1)));
        }
        return  bk[i][j];
    }

}
